package zuo.algo.c11;

import java.util.HashMap;
import java.util.Map;

/**
 * 00:54-设计一种结构，在该结构中有如下三种功能：
 *  insert(key)：将某个key加入到该结构中，做到不重复加入
 *  delete(key)：将原本结构中的某个key移除
 *  getRandom(key)：等概率随机返回一个key
 */
public class RandomPool<K> {

    private final Map<K, Integer> keyIndexMap = new HashMap<>();
    private final Map<Integer, K> indexKeyMap = new HashMap<>();

    private int size = 0;

    public void insert(K key) {
        if (keyIndexMap.containsKey(key)) {
            return;
        }
        keyIndexMap.put(key, size);
        indexKeyMap.put(size, key);
        size++;
    }

    public K getRandom() {
        if (size == 0) {
            return null;
        }
        int idx = (int) (Math.random() * size);
        return indexKeyMap.get(idx);
    }

    public void delete(K key) {
        Integer idx = keyIndexMap.remove(key);
        Integer maxIdx = --size;
        if (idx != null) {
            K delKey = indexKeyMap.remove(maxIdx);
            if (idx < size) {
                indexKeyMap.put(idx, delKey);
                keyIndexMap.put(delKey, idx);
            }
        }
    }

    public static void main(String[] args) {
        RandomPool<String> pool = new RandomPool<>();
        pool.insert("zuo");
        pool.insert("cheng");
        pool.insert("yun");
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());
        System.out.println(pool.getRandom());

        pool.delete("zuo");
        System.out.println(pool.getRandom());

        pool.insert("aaa");
        pool.delete("aaa");
        System.out.println(pool.getRandom());
    }
}
